package LeetCode;

import java.util.HashMap;
import java.util.Map;

public class Code560_subarraySum {

    // 以每个元素为开始
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k){
                    res++;
                }
            }
        }
        return res;
    }
    // 每个元素当作末尾元素
    public int subarraySum2(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j >= 0; j--) {
                sum += nums[j];
                if (sum == k){
                    res++;
                }
            }
        }
        return res;
    }

    // pre[i]=pre[i−1]+nums[i]
    // [j..i] pre[i]−pre[j−1]==k -> pre[j−1]==pre[i]−k

    public int subarraySum3(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        // 记录（0~i）前缀和及对应出现次数
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        int sum = 0;
        map.put(0,1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum-k)){
                res += map.get(sum-k);
            }
            if (!map.containsKey(sum)){
                map.put(sum, 1);
            } else {
                map.put(sum, map.get(sum) + 1);
            }
        }
        return res;
    }
}
